package com.example.demo.shuatiban.zuocheng;

import java.util.Random;

/**
 * @author xujm
 * @version V2.4
 *
 *  给定一个正数组arr,代表若干人的体重
 *  定义轮船的沉重limit
 *  每艘船最多做两个人，不能超过载重
 *  想让所有的人过河，求用最少的船
 *
 * @since 2.4.0 2022/3/26 12:04
 */
public class 过河 {

    /**
     * 方法一:
     * 排序，找出中间位置L，R=L+1,   arr[L]<=limit/2  arr[R] >imit/2
     * L往左遍历，找出L可以和R组合的点，然后R一直往右到R`,
     * R`无法和L组合， 那么R`下标-R下标 就是有多少个数可以和L组合
     *
     * 组合完后，L继续往左。L遍历完后，剩下的R 单独做船
     * R遍历完后，剩下的L两个人一搜船
     *
     *
     * @return
     */
    public static int minBoot(int [] arr,int limit){

        int L=0,R=0;
        int res =0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>(limit/2)){
                L = i-1;
                R = i;
                break;
            }
        }
        int middle = L;
        boolean [] use = new boolean[arr.length];
        int count=0;
        while(L >=0 && R < arr.length){

            if(arr[L] + arr[R] > limit){
                L--;
                continue;
            }


            while(R+count < arr.length && arr[L] + arr[R+count] <= limit){
                count++;
            }
            // count>0 说明存在值可以组合
            //   01 23  45 6
            //   22 55  66 9
            while(L >=0 && R < arr.length && count > 0){
                use[L] = true;
                use[R] = true;
                L--;
                R++;
                count--;
                res++;
            }
        }

        int left =0;
        for(int i=0;i<=middle;i++){
            if(!use[i]){
                left++;
            }
        }
        int right=0;
        for(int i=middle+1;i<use.length;i++){
            if(!use[i]){
                right++;
            }
        }

        if(left % 2 == 0){
            res = res+left/2+right;
        }else{
            res = res+left/2+right+1;
        }
        return res;
    }

    /**
     * 方法二: 头尾指针
     * @param arr
     * @param limit
     * @return
     */
    public static int min(int [] arr,int limit){

        int res = 0;
        int L = 0;
        int R = arr.length-1;
        boolean [] use = new boolean[arr.length];
        while(L < R){

            if(arr[L] + arr[R] <= limit){
                use[L] = true;
                use[R] = true;
                res++;
                L++;
                R--;
                continue;
            }
            if(arr[L] + arr[R] > limit){
                R--;
                continue;
            }
        }
        for(int i = 0;i<use.length;i++){
            if(!use[i]){
                res++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int [] arr = {1,1,5,5,6,9,9};

        System.out.println(minBoot(arr,10));
        System.out.println(min(arr,10));

        Random random = new Random();
        random.nextInt(10);
        for(int i=0;i<1000;i++){
            int [] temp = new int[10];
            for(int j=0;j<10;j++){
                temp[j]= random.nextInt(10);
            }
            if(min(arr,10) == minBoot(arr,10)){
                // System.out.println(true);
            }else{
                for(int k=0;k<10;k++){
                    System.out.print(arr[k]+" ");
                }
            }

        }
    }


}
